
/**
 * 
 * 数字排列
 * 
 * 题目描述

小明负责公司年会，想出一个趣味游戏：

屏幕给出 1 ~ 9 中任意 4 个不重复的数字，大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第 N 位置的数字，其中 N 为给出数字中最大的（如果不到这么多数字则给出最后一个即可）。

注意：

2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接，且屏幕不能同时给出 2 和 5；
6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接，且屏幕不能同时给出 6 和 9。
如给出：1，4，8，7，则可以拼接的数字为：

1，4，7，8，14，17，18，41，47，48，71，74，78，81，84，87，147，148，178 ... (省略后面的数字)

那么第 N （即8）个的数字为 41。

输入描述
输入以逗号分隔的 4 个 int 类型整数的字符串。

输出描述
输出为这几个数字可拼成的数字从小大大排列位于第 N （N为输入数字中最大的数字）位置的数字，

如果输入的数字不在范围内或者有重复，则输出-1。

用例
输入	1,4,8,7
输出	41
说明	
可以构成的数字按从小到大排序为：
1，4，7，8，14，17，18，41，47，48，71，74，78，81，84，87，147，148，178  ... （省略后面的数字），
故第8个为41
输入	2,5,1
输出	-1
说明	2和5不能同时出现
输入	3,0,9
输出	-1
说明	0不在1到9范围内
输入	3,9,7,8
输出	39
说明	
注意9可以当6使用，所以可以构成的数字按从小到大排序为：3，6，7，8，9，36，37，38，39，63，67，68，73，76，78，79，83 ... （省略后面的数字），
故第9个为39

 * 
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

/**
  * 
  题目解析
首先本题需要我们做一些输入校验：

输入同时给出 2 和 5
输入同时给出 6 和 9
输入的数字不在范围内或者有重复
以上情况的输入返回-1，表示输入校验失败。

本题需要我们求解某个序列的所有排列情况，比如无重复元素序列：[a, b, c]，则所有排列为：

a
b
c
ab
ba
ac
ca
bc
cb
abc
acb
bac
bca
cab
cba
我们可以用回溯算法求解某个序列的所有排列，关于回溯算法求解排列可以参考：

LeetCode - 46 全排列_全排列 46 力扣-CSDN博客

这篇博客要我们求解的某个序列的全排列，全排列和排列的区别在于：

所谓排列，即从n个数中选m个数，组成不同顺序的排列，此时 m <= n

而全排列，特指 m == n 的排列，比如序列：[a, b, c] 的全排列为：

abc
acb
bac
bca
cab
cba
因此，LeetCode 46 我们需要将 path.size() <= nums.length 的所有排列情况都记录到res中。

另外，本题还有一个不同：

2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接
6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接
此时，我们只需要在求解排列时，看当前排列选定元素是否为2，5，6，9中某个数，若是，则还需要尝试将当前选定元素做变化如下：

2->5：即当前选定元素为2，则同时尝试当前选定元素为5

5->2：即当前选定元素为5，则同时尝试当前选定元素为2

6->9：即当前选定元素为6，则同时尝试当前选定元素为9

9->6：即当前选定元素为9，则同时尝试当前选定元素为6

最后，关于N的取值，N为输入数中最大值，若N超过了最终求解的排列数个数，则N = 排列数个数

  */
public class 数字排列 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
 
        System.out.println(solution(nums));
    }
 
    public static int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int n = Integer.MIN_VALUE;
 
        for (int num : nums) {
            if (num < 1 || num > 9) {
                //  输入的数字不在范围内
                return -1;
            } else {
                set.add(num);
                n = Math.max(n, num);
            }
        }
 
        // 输入的数字有重复
        if (set.size() != 4) return -1;
 
        // 屏幕不能同时给出 2 和 5
        if (set.contains(2) && set.contains(5)) return -1;
 
        // 屏幕不能同时给出 6 和 9
        if (set.contains(6) && set.contains(9)) return -1;
 
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(2, 5);
        map.put(5, 2);
        map.put(6, 9);
        map.put(9, 6);
 
        boolean[] vis = new boolean[nums.length];
 
        String path = "";
 
        // 记录排列
        ArrayList<Integer> res = new ArrayList<>();
 
        // 排列求解
        dfs(nums, vis, path, map, res);
 
        // 给出这几个数字可拼成的数字从小到大排列位于第 N 位置的数字
        res.sort((a, b) -> a - b);
 
        // N为给出数字中最大的，如果不到这么多数字则给出最后一个即可
        n = Math.min(n, res.size());
        return res.get(n - 1);
    }
 
    // 排列求解
    public static void dfs(int[] nums, boolean[] vis, String path, HashMap<Integer, Integer> map, ArrayList<Integer> res) {
        if (!path.isEmpty()) {
            res.add(Integer.parseInt(path));
        }
 
        if (path.length() == nums.length) {
            return;
        }
 
        for (int i = 0; i < nums.length; i++) {
            if (vis[i]) continue;
 
            vis[i] = true;
 
            dfs(nums, vis, path + nums[i], map, res);
 
            // 2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接
            // 6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接
            if (map.containsKey(nums[i])) {
                dfs(nums, vis, path + map.get(nums[i]), map, res);
            }
 
            vis[i] = false;
        }
    }

}
